package two.chapter_1.c1_1;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

/**
 * 二分查找
 */
public class BinarySearch {

    public static int rank(int key, int a[]) {
        return rank(key, 0, a.length - 1, a);
    }

    private static int rank(int key, int lo, int hi, int[] a) {

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int compare = key - a[mid];
            if (compare > 0) {
                lo = mid + 1;
            } else if (compare < 0) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }


    public static void main(String [] args){
        int [] whiteList= In.readInts(args[0]);
        Arrays.sort(whiteList);
        while (!StdIn.isEmpty()){
            int key=StdIn.readInt();
            if (rank(key,whiteList)<0){
                StdOut.println(key);
            }
        }

    }


}
